// 如果k是偶数
// 1. 如果负数的个数是偶数，那结果一定是正数
// 2. 如果负数的个数是奇数，那就选偶数个负数，结果还是正数
// 如果k是奇数
// 1. 如果全是负数，那只能得到负数
// 2. 如果有正数，先把最大的正数取出来
// 接下来就又变到选k - 1个偶数的阶段
#include <iostream>
#include <algorithm>
using namespace std;
using LL = long long;
// 成对取出来的一定是最大的
const int N = 100010, mod = 1000000009;
int n, k;
int a[N];
int main()
{
    cin >> n >> k;
    for(int i = 0; i < n; ++i) cin >> a[i];
    sort(a, a + n);
    int l = 0, r = n - 1;
    int flag = 1;
    LL ans = 1;
    if(k % 2)
    {
        ans = a[r];
        r--;
        k--;
        if(ans < 0) flag = -1;
    }
    while(k)
    {
        // x 最大是10^10次方，会爆LL
        LL x = 1ll *a[l] * a[l + 1], y = 1ll * a[r] * a[r - 1];
        if(x * flag > y * flag)
            ans = x % mod * ans % mod, l += 2;
        else
            ans = y % mod * ans % mod, r -= 2;
        k -=2;
    }
    cout << ans << endl;
    return 0;
}